import java.util.*;
public class Solution {
    //判断链表是否有环

  class ListNode {
     int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

  //方法一 快慢指针
    public boolean hasCycle(ListNode head) {
      if(head == null || head.next == null){
          return false;
      }
      ListNode fast = head;
      ListNode slow = head;
      while(fast != null && fast.next != null ){
          slow = slow.next;
          fast = fast.next.next;
          if(slow == fast){
              return true;
          }
      }
      return false;
    }

    //方法二 哈希表
    public boolean hasCycle1(ListNode head) {
      Set<ListNode> set = new HashSet<>();
      while(head != null){
          if(!set.add(head)){
              /*
              * 当调用 Set 的 add 方法添加元素时，如果该元素已经存在于集合中
              * add 方法会返回 false；如果元素不存在，add 方法会将元素添加到集合中并返回 true。
              * */
              return true;
          }
          head = head.next;
      }
      return false;
    }
}
